Two Sum || 3 Sum

发表于

Two Sum

Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Tips
  • 第二个脚标注意从+1开始，部分用例的target等于某个值的双倍
  • 在找到合适的一对数时break跳出，无需继续进行循环
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result=new int[2];
        for(int i=0;i<nums.length;i++){
            result[0]=i;
            result[1]=-1;
            int remain=target-nums[i];
            for(int j=i+1;j<nums.length;j++){
                if(nums[j]==remain){
                    result[1]=j;
                    break;
                }
            }
            if(result[1]!=-1)
                break;
        }
        return result;
    }
}

3 Sum

Question

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
Tips
  • 对数组排序后，两个指针low，high从两侧向中间移动，循环条件为low<high
  • 求当前点已经low、high的和并判断是否符合条件，符合条件即加入集合中，并且利用hashtable判断是否有重复出现再决定插入与否
  • 该方法也可用于 2 sum
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        HashSet<ArrayList<Integer>> test=new HashSet<ArrayList<Integer>>();
        
        Arrays.sort(nums);
        
        for(int i=0;i<nums.length-2;i++){
            int low=i+1,high=nums.length-1;
            while(low<high){
                int sum=nums[i]+nums[low]+nums[high];
                if(sum==0){
                    ArrayList<Integer> item=new ArrayList<Integer>();
                    item.add(nums[i]);
                    item.add(nums[low]);
                    item.add(nums[high]);
                    
                    if(!test.contains(item)){
                        test.add(item);
                        result.add(item);
                    }
                    
                    low++;
                    high--;
                }else if(sum<0){
                    low++;
                }else{
                    high--;
                }
            }
        }
        return result;
    }
}

3 Sum 的原题目对duplicate有要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(num.length<3||num == null)
            return res;
        
        Arrays.sort(num);
        
        for(int i = 0; i <= num.length-3; i++){
            if(i==0||num[i]!=num[i-1]){//remove dupicate
                int low = i+1;
                int high = num.length-1;
                while(low<high){
                    int sum = num[i]+num[low]+num[high];
                    if(sum == 0){
                        ArrayList<Integer> unit = new ArrayList<Integer>();
                        unit.add(num[i]);
                        unit.add(num[low]);
                        unit.add(num[high]);
                        
                        res.add(unit);
                        
                        low++;
                        high--;
                        
                        while(low<high&&num[low]==num[low-1])//remove dupicate
                            low++;
                        while(low<high&&num[high]==num[high+1])//remove dupicate
                            high--;
                            
                    }else if(sum > 0)
                        high --;
                     else
                        low ++;
                }
            }
        }
        return res;
    }

Java: length/size用法

  • java中的length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了length这个属性.
  • java中的length()方法是针对字符串String说的,如果想看这个字符串的长度则用到length()这个方法.
  • java中的size()方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!

List与ListArray

综述

List是一个接口，而ListArray是一个类。
ListArray继承并实现了List。
所以List不能被构造，但可以向上面那样为List创建一个引用，而ListArray就可以被构造。
List list; //正确 list=null;
List list=new List(); // 是错误的用法

List list = new ArrayList();这句创建了一个ArrayList的对象后把上溯到了List。此时它是一个List对象了，有些ArrayList有但是List没有的属性和方法，它就不能再用了。
而ArrayList list=new ArrayList();创建一对象则保留了ArrayList的所有属性。
这是一个例子：

import java.util.*;

public class TestList{
​ public static void main(String[] args){
​ List list = new ArrayList();
​ ArrayList arrayList = new ArrayList();

​ list.trimToSize(); //错误，没有该方法。
​ arrayList.trimToSize(); //ArrayList里有该方法。
​ }
}

问题的关键
为什么要用 List list = new ArrayList() ,而不用 ArrayList alist = new ArrayList()呢？
问题就在于List有多个实现类，现在你用的是ArrayList，也许哪一天你需要换成其它的实现类，如 LinkedList或者Vector等等，这时你只要改变这一行就行了：
List list = new LinkedList(); 其它使用了list地方的代码根本不需要改动。
假设你开始用 ArrayList alist = new ArrayList(), 这下你有的改了，特别是如果你使用了 ArrayList特有的方法和属性。

另外的例子就是,在类的方法中,如下声明:
private void doMyAction(List list){}
这样这个方法能处理所有实现了List接口的类,一定程度上实现了泛型函数.

如果开发的时候觉得ArrayList,HashMap的性能不能满足你的需要,可以通过实现List,Map(或者Collection)来定制你的自定义类.

Tips

List 的初始化定义方式应为List> list = new ArrayList>(); / List> list = new ArrayList<>(); 不应为 List<List<Integer>> list = new ArrayList<ArrayList<Integer>>();